package com.yuan.algorithms.算法导论_第一部分;

import java.util.Scanner;

/**
 * @author YouYuan <br>
 *         E-mail:1265161633@qq.com <br>
 *         创建时间：2015年11月19日 上午8:56:12 <br>
 *         说明:归并排序
 */
public class MergeSort {

	static Scanner in = new Scanner(System.in);

	public static void main(String[] args) {
		while (in.hasNext()) {
			int n = in.nextInt();
			double[] arr = new double[n];
			for (int i = 0; i < n; i++) {
				arr[i] = in.nextDouble();
			}
			mergeSort(arr, 0, arr.length - 1);
			for (double i : arr) {
				System.out.print(i + " ");
			}
		}
	}

	private static void mergeSort(double[] arr, int low, int hight) {
		//若low>=hight,则该子数组最多有一个元素，所以已经排好序
		if (low < hight) {
			// 分解待排序的n个元素的序列成各具n/2个元素的两个子序列
			mergeSort(arr, low, (low + hight) / 2);
			mergeSort(arr, (low + hight) / 2 + 1, hight);
			// 合并两个有序序列
			merge(arr, low, (low + hight) / 2, hight);
		}
	}

	/**
	 * 合并两个有序序列并代替当前的数组arr
	 * 
	 * @param arr
	 *            存储序列的数组
	 * @param low
	 *            第一个有序序列的起始下标
	 * @param mid
	 *            有序序列的分隔点
	 * @param hight
	 *            第二个有序序列的终点
	 */
	private static void merge(double[] arr, int low, int mid, int hight) {
		double[] t = new double[hight - low + 1];
		int s = low;// 已排序的前半部分的下标
		int e = mid + 1;// 已排序的后半部分的下标
		int current = 0;
		while (s <= mid && e <= hight) {// 排序的范围
			if (arr[s] < arr[e]) {// 将较小的值存储到临时数组中，继续排列下一个值
				t[current++] = arr[s++];
			} else {
				t[current++] = arr[e++];
			}
		}
		// 因为已经是有序序列，可以将剩余的值直接存储到临时数组中
		while (s <= mid) {
			t[current++] = arr[s++];
		}
		while (e <= hight) {
			t[current++] = arr[e++];
		}
		// 将新的有序序列存储到原数组中
		for (int i = 0, len = t.length; i < len; i++) {
			arr[low + i] = t[i];
		}
	}

}
